java合并对来自的行进行排序。txt文件
我有一个有多行排序的文件。 现在我想把所有这些行排序到一个新文件中的一个合并行中。而不是一次加载所有的数字
这是我文件的一部分:
12,86,280,304,350,359,371,391,405,548,
255,264,325,346,435,466,483,
39,114,214,298,317,377,428,438,575,
35,165,183,281,336,367,386,418,438,593,
44,77,97,117,122,156,251,415,533,
109,155,163,172,212,226,340,358,452,577,592,
33,74,91,204,256,307,357,388,534,552,554,570,
50,99,246,309,345,358,395,405,419,425,566,
现在我想合并排序这些,所以首先我需要知道文件有多少行。然后我需要得到所有的第一个元素并进行比较。我写入新文件的最低值。然后我要从我刚刚写的那句话中得到第二个数字。并将其与其他行的第一个数字进行比较。我该怎么做。我为ArrayList编写了一个合并排序:
//as long as there is unsorted data
while (listOfOutputs.size() > 0) {
//Set the lowest undefined
List<Integer> lowest = null;
for (List<Integer> list : listOfOutputs) {
//if the lowest is undefined, I'm the lowest
if (lowest == null) {
lowest = list;
//Else am I lower then the lowest? Then I'm the lowest
} else if (list.get(0) < lowest.get(0)) {
lowest = list;
}
}
//Finally the lowest is added to the sorted list and removed to from his own list.
assert lowest != null;
sortedList.add(lowest.remove(0));
//Is the size of the list which contained to lowest now 0, remove him from the listOfOutputs
if (lowest.size() == 0) listOfOutputs.remove(lowest);
}
但我不知道如何把它改写成一个能给我的文件排序的文件。我如何做到这一点,而不必将它们加载到列表中
斯文
# 1 楼答案
您可以使用简单的双向合并,一次将两行合并为一行,重复此过程,直到生成一个排序的行
或者
假设k是行数,可以实现k路合并,可能使用堆优化查找第一个元素最小的行。每个堆元素都包含一个对行的引用,相当于该行当前元素的索引(或指针)。堆按每行的当前元素排序,以便堆头引用具有当前最小元素的行。堆由所有k行的第一个元素初始化
对于每个合并步骤,都会删除堆头的行(包含最小元素的行),将最小元素附加到输出行,并基于下一个元素将包含最小元素的行添加回堆中
当到达一行的末尾时,合并将简化为k-1路合并,最终只得到一行,并复制到合并的输出中